package Leetcode.DayTest;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/9/15 12:03
 * @Description:
 */

public class Test_415 {
    public static void main(String[] args) {
        int[] a = {3,2,5,6};
        int[] b = {2,-6,4,-5,-3,2,-7};
        System.out.println(maxScore_false(a, b));

    }
    public static  int[] getSneakyNumbers(int[] nums) {
        int[] arr = new int[101];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]]++;
        }
        int[] ans = new int[2];
        int index=0;
        for (int i = 0; i < 101; i++) {
            if (arr[i] >= 2) {
                ans[index++] = i;
            }

        }
        return ans;
    }

    /**
     * 给你一个大小为 4 的整数数组 a 和一个大小 至少为 4 的整数数组 b。
     *
     * 你需要从数组 b 中选择四个下标 i0, i1, i2, 和 i3，并满足 i0 < i1 < i2 < i3。你的得分将是 a[0] * b[i0] + a[1] * b[i1] + a[2] * b[i2] + a[3] * b[i3] 的值。
     *
     * 返回你能够获得的 最大 得分。
     *
     * 示例 1：
     *
     * 输入： a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7]
     *
     * 输出： 26
     *
     * 解释：
     * 选择下标 0, 1, 2 和 5。得分为 3 * 2 + 2 * (-6) + 5 * 4 + 6 * 2 = 26。
     *
     * 示例 2：
     *
     * 输入： a = [-1,4,5,-2], b = [-5,-1,-3,-2,-4]
     *
     * 输出： -1
     *
     * 解释：
     * 选择下标 0, 1, 3 和 4。得分为 (-1) * (-5) + 4 * (-1) + 5 * (-2) + (-2) * (-4) = -1。
     */
    public static long maxScore_false(int[] a, int[] b) {
        long ans = Long.MIN_VALUE;
        int len = b.length;
        long[] temp = new long[len];
        temp[1] = (long) a[0] * b[0] + (long) a[1] * b[1];
        for (int end = 2; end < len; end++) {
            long max = Long.MIN_VALUE;
            for (int i = 0; i < end - 1; i++) {
                for (int j = i + 1; j < end; j++) {
                    max = Math.max(max, (long) a[0] * b[i] + (long) a[1] * b[j]);
                }
            }
            temp[end] = Math.max(temp[end - 1], max);
        }
        for (int i = 2; i < len-1; i++) {
            for (int j = i+1; j < len; j++) {
                ans = Math.max(ans, temp[i - 1] + (long) a[2] * b[i] + (long) a[3] * b[j]);
            }
        }
        return ans;
    }
    public long maxScore(int[] a, int[] b) {
        // 获取数组b的长度，这将用于初始化动态规划数组dp的列数
        int n = b.length;

        // 初始化一个4行n列的二维数组dp，用于存储中间计算结果
        // dp[i][j]将代表使用数组a的前i+1个元素和数组b的前j+1个元素计算出的最大得分
        long[][] dp = new long[4][n];

        // 初始化dp数组的第一个元素，即只使用a[0]和b[0]计算得分
        dp[0][0] = (long)a[0] * b[0];

        // 填充dp数组的第0行，即对于每个b[j]，计算只使用a[0]时的最大得分
        // 同时确保每个位置的得分都是递增的
        for(int i = 1; i < n; i++) {
            dp[0][i] = Math.max(dp[0][i-1], (long)a[0] * b[i]);
        }

        // 遍历数组a的剩余元素（索引从1到3，因为数组a的大小是4）
        for(int i = 1; i < 4; i++) {
            // 计算dp[i][i]，即使用a的前i+1个元素和b的前i+1个元素计算得分
            dp[i][i] = dp[i-1][i-1] + (long)a[i] * b[i];

            // 填充dp数组的第i行，即对于每个b[j]（j > i），计算使用a的前i+1个元素时的最大得分
            for(int j = i + 1; j < n; j++) {
                // 计算dp[i][j]，考虑使用a[i]和b[j]的情况
                dp[i][j] = dp[i-1][j-1] + (long)a[i] * b[j];

                // 更新dp[i][j]，使其保持最大值，考虑不使用b[j]的情况
                dp[i][j] = Math.max(dp[i][j], dp[i][j-1]);
            }
        }

        // 返回dp数组的最后一个元素，即使用数组a和数组b所有元素计算出的最大得分
        return dp[3][n-1];
    }



    class Trie {
        Trie[] child;
        Trie() {
            child = new Trie[26];
        }
        void addWord(String s,int p) {
            if(p>=s.length()) return;
            int c = s.charAt(p)-'a';
            if(this.child[c] == null) {
                this.child[c] = new Trie();
            }
            this.child[c].addWord(s,p+1);
        }
    }

    /**
     * 给你一个字符串数组 words 和一个字符串 target。
     *
     * 如果字符串 x 是 words 中 任意 字符串的
     * 前缀
     * ，则认为 x 是一个 有效 字符串。
     *
     * 现计划通过 连接 有效字符串形成 target ，请你计算并返回需要连接的 最少 字符串数量。如果无法通过这种方式形成 target，则返回 -1。
     *
     * 示例 1：
     *
     * 输入： words = ["abc","aaaaa","bcdef"], target = "aabcdabc"
     *
     * 输出： 3
     *
     * 解释：
     *
     * target 字符串可以通过连接以下有效字符串形成：
     *
     * words[1] 的长度为 2 的前缀，即 "aa"。
     * words[2] 的长度为 3 的前缀，即 "bcd"。
     * words[0] 的长度为 3 的前缀，即 "abc"。
     */
    public int minValidStrings(String[] words, String target) {
        // 创建一个Trie对象，用于存储words数组中的所有字符串
        Trie root = new Trie();
        // 将words数组中的每个字符串添加到Trie中
        for(String s: words) {
            root.addWord(s, 0);
        }

        // 获取目标字符串target的长度
        int n = target.length();
        // 将目标字符串转换为字符数组
        char[] ch = target.toCharArray();

        // 初始化一个动态规划数组dp，大小为n+1，用于存储从索引i到末尾的最小有效字符串数量
        // dp[i]表示从索引i到target末尾最少需要添加的字符数量
        int[] dp = new int[n+1];
        // 将dp数组除dp[n]以外的所有元素初始化为Integer.MAX_VALUE
        Arrays.fill(dp, Integer.MAX_VALUE);
        // dp[n]初始化为0，因为从target末尾到末尾不需要添加任何字符
        dp[n] = 0;

        // 从target的倒数第一个字符开始向前遍历
        for(int i = n - 1; i >= 0; i--) {
            // 从Trie的根节点开始
            Trie t = root;
            // 初始化指针p为当前索引i
            int p = i;
            // 当p未到达target末尾且当前Trie节点存在子节点与target[p]匹配时继续循环
            while(p < n && t.child[ch[p]-'a'] != null) {
                // 如果从p+1到末尾的字符串已经计算过最小有效字符串数量且不为最大值
                if(dp[p+1] != Integer.MAX_VALUE) {
                    // 更新dp[i]，取当前值和dp[p+1]+1的最小值
                    dp[i] = Math.min(dp[i], dp[p+1] + 1);
                }
                // 移动到Trie的下一个子节点
                t = t.child[ch[p]-'a'];
                // 移动指针p到下一个字符
                p++;
            }
        }
        System.out.println(Arrays.toString(dp));

        // 如果dp[0]仍然是Integer.MAX_VALUE，说明无法通过添加字符使words中的字符串变为target
        // 返回-1，否则返回dp[0]，即从索引0开始到末尾的最小有效字符串数量
        return dp[0] == Integer.MAX_VALUE ? -1 : dp[0];
    }
}
